package solutionsdemo;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 黎鹤舞
 * Date: 2024-01-26
 * Time: 19:36
 */

/**
 * 平衡二叉树
 */
public class BalancedTree {

    /**
     * 方法二:
     * 子问题思路:如果两课子树已经树，return -1
     */

    public int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }

        int leftHeight = getHeight(root.left);
        if(leftHeight < 0) {
            return -1;
        }
        int rightHeight = getHeight(root.right);

        //这里左右子树均>0 说明左右子树的子节点均平衡，
        if(leftHeight >= 0 && rightHeight >=0 && Math.abs(leftHeight - rightHeight) <2) {
            return Math.max(leftHeight,rightHeight) + 1;
        }else {
            return -1;
        }

    }
    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }
        if(getHeight(root) < 0) {
            return false;
        }
        return true;
    }
    /**
     * 方法一:
     * 利用遍历思想，对二叉树的每个节点的左右子树都求出高度，并进行判断
     * 缺点:时间复杂度O(n^2);如果已经证明了其中一个子树为非平衡二叉树，程序仍会继续遍历
     */
//    public int getHeight(TreeNode root) {
//        if(root == null) {
//            return 0;
//        }
//        int leftHeight = getHeight(root.left);
//        int rightHeight = getHeight(root.right);
//        return Math.max(leftHeight,rightHeight) + 1;
//    }
//    public boolean isBalanced(TreeNode root) {
//        if(root == null) {
//            return true;
//        }
//        int leftHeight = getHeight(root.left);
//        int rightHeight = getHeight(root.right);
//        int differ = Math.max(leftHeight,rightHeight) - Math.min(leftHeight,rightHeight);
//        if(differ > 1) {
//            return false;
//        }
//        return isBalanced(root.left) && isBalanced(root.right);
//    }
}
